package com.nowcoder.code.lcof;

import com.algorithm.model.ListNode;

import java.util.ArrayList;
import java.util.List;

public class JZ52 {

    public static void main(String[] args) {
        List<ListNode> list = new ArrayList<>();
        list.add(new ListNode(1));
        for (int i = 1; i < 7; i++) {
            ListNode listNode = new ListNode(i+1);
            list.get(i - 1).next = listNode;
            list.add(listNode);
        }
//        list.get(2).next = list.get(5);


        System.out.println(new JZ52().FindFirstCommonNode(list.get(0), list.get(0)));
    }


    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        ListNode p1 = pHead1;
        ListNode p2 = pHead2;

        int i1 = 0;
        int i2 = 0;
        while (p1 != null) {
            i1++;
            p1 = p1.next;
        }

        while (p2 != null) {
            i2++;
            p2 = p2.next;
        }

        int min = Math.min(i2, i1);
        int max = Math.max(i2, i1);
        int i0 = max - min;

        p1 = i2 < i1 ? pHead1 : pHead2;
        p2 = i2 < i1 ? pHead2 : pHead1;


        while (max != 0) {
            if (p1 == p2) {
                return p1;
            }
            max--;
            p1 = p1.next;
            if (i0 == 0) {
                p2 = p2.next;
            } else {
                i0--;
            }


        }

        return null;


    }

}
